package main

import "fmt"

// 如何进行归并排序

func main() {
	array := []int{5, 4, 9, 8, 7, 6, 0, 1, 3, 2}
	mergeSort(array, 0, len(array)-1)
	fmt.Println(array)
}

func mergeSort(array []int, p, r int) {
	if p < r {
		q := (p + r) / 2
		mergeSort(array, p, q)
		mergeSort(array, q+1, r)
		merge(array, p, q, r)
	}
}

func merge(array []int, p, q, r int) {
	// array[p~q] 已排好序，array[q+1~r] 也已排好序
	n1 := q - p + 1
	n2 := r - q

	// 把两段数组中的元素分别移到新数组中
	L := make([]int, n1)
	R := make([]int, n2)
	for i, k := 0, p; i < n1; i, k = i+1, k+1 {
		L[i] = array[k]
	}
	for i, k := 0, q+1; i < n2; i, k = i+1, k+1 {
		R[i] = array[k]
	}

	// 把新数组中的元素移入原数组中
	var i, j, k int
	for i, j, k = 0, 0, p; i < n1 && j < n2; k++ {
		if L[i] < R[j] {
			array[k] = L[i]
			i++
		} else {
			array[k] = R[j]
			j++
		}
	}

	// 分配完之后，把新数组剩余的部分依次移入原数组中
	if i < n1 {
		for j = i; j < n1; j, k = j+1, k+1 {
			array[k] = L[j]
		}
	}
	if j < n2 {
		for i = j; i < n2; i, k = i+1, k+1 {
			array[k] = R[i]
		}
	}
}
